package exams.list;

public class SortListSolution {

    public ListNode sortInList (ListNode head) {
        // write code here
        if(head == null || head.next == null) {
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        while(p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        ListNode head2 = p1.next;
        p1.next = null;
        return merge(sortInList(head), sortInList(head2));
    }

    /**
     * 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
     * 数据范围：节点总数 0≤n≤5000，每个节点的val满足 ∣val∣<=1000
     * 输入：[{1,2,3},{4,5,6,7}]
     * 返回值：{1,2,3,4,5,6,7}
     * */
    public ListNode mergeNodeArr(ListNode[] nodeArr) {
        if(nodeArr.length == 1) {
            return nodeArr[0];
        }
        ListNode[] newArr = new ListNode[(nodeArr.length + 1)/2];
        int i;
        for(i = 0; i < nodeArr.length - 1; i=i+2) {
            ListNode p1 = nodeArr[i];
            ListNode p2 = nodeArr[i+1];
            newArr[i/2] = merge(p1, p2);
        }
        if(i == nodeArr.length - 1) {
            newArr[i/2] = nodeArr[i];
        }
        return mergeNodeArr(newArr);
    }

    /**
     * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
     * 数据范围： 0≤n≤1000，−1000≤节点值≤1000要求：空间复杂度 O(1)，时间复杂度 O(n)
     * 如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}
     * */
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(head1 != null && head2 != null) {
            if(head1.val <= head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if(head1 != null) {
            cur.next = head1;
        }
        if(head2 != null) {
            cur.next = head2;
        }

        return head.next;
    }

}
